package com.heu.zth;

import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Map.Entry;
import java.util.Set;

// Spfa + SLF
public class Spfa_SLF {
	private Deque<Car> buff = new LinkedList<Car>();
	private HashSet<Integer> doneSet = new HashSet<Integer>();
	
	void spfa(Car start) {
		start.setCurrentCost(0);
		buff.addFirst(start);
		doneSet.add(start.getId());
		while(!buff.isEmpty()) {
			Car car = buff.pollFirst();
			doneSet.remove(car.getId());
			HashMap<Car, Double> neighbors = car.getNeighbors();
			Set<Entry<Car, Double>> entries = neighbors.entrySet();
			for (Iterator<Entry<Car, Double>> iterator = entries.iterator(); iterator.hasNext();) {
				Entry<Car, Double> entry = iterator.next();
				Car c = entry.getKey();
				double v = entry.getValue();
				if (car.getCurrentCost() < Car.INFCOST && (car.getCurrentCost() + v < c.getCurrentCost())) {
					c.setCurrentCost(car.getCurrentCost() + v);
					c.parent = car;
					if (!doneSet.contains(c.getId())) {
						doneSet.add(c.getId());
						if (!buff.isEmpty()) {
							if (c.getCurrentCost() > buff.getFirst().getCurrentCost()) {
								buff.addLast(c);
							} else {
								buff.addFirst(c);
							}
						} else {
							buff.addLast(c);
						}
					}
				}
			}
		}
	}
}